Encryption can enhance the privacy of law-abiding citizens in their use of phones, faxes, computers and other devices It is also well recognized, however, that encryption may be misused in a variety of ways by criminals, spies and terrorists who wish to communicate to avoid being understood through legitimate wiretapping.
Various technologies have been considered in the past to make encryption compatible with law enforcement. For instance, one might envisage allowing only cryptosystems that are sufficiently "weak," so that all ciphertext they produce may be decrypted by the proper authority without extraordinary computational efforts. Alternatively, one may recommend using cryptosystems that are quite strong, but only with sufficiently short secret keys. Another approach, which is described in U.S. Pat. Nos. 5,276,737 and 5,315,658 ("Fair Cryptosystems), as in the U.S. Government's Clipper Chip program, envisions cryptosystems where trustees hold pieces of information that are guaranteed to contain correct pieces of decryption keys. Thus, although a single trustee may not be able to reconstruct a single secret key, any relevant secret key may be reconstructed by the trustees taken collectively.
There is, however, a different type of problem unsolved by all these technologies: firmly guaranteeing that a given ciphertext has indeed been produced by the approved cryptosystems. This is a very important problem, and it will become even more so when, due to the spread of cryptography, millions of ciphertexts will be generated every day. Ciphertexts generated by Government-approved devices (such as the Clipper Chip) should not be a significant concern for law enforcement because the approved devices will make use either of either weak cryptosystems, of strong cryptosystems with a short key, or of key-escrow systems; therefore, agencies implementing such devices know, under the circumstances envisioned by the law, that the meaning of those ciphertexts will become intelligible. Instead, law enforcement agencies will be concerned about those ciphertexts that have not been produced by Government-approved systems, because such agencies will never be able to understand them, no matter how many court orders for wiretapping are implemented.
Nonetheless, it would be desirable to law enforcement if these "alternative" ciphertexts could be easily distinguished from the "standard" ones. In such case, the law enforcement agency would be more aware that a given person X goes out of his way (possibly incurring great inconvenience and great costs) to use encryption equipment that is not Government-approved and that the person does so in order not to be understood, even in the legitimate circumstances envisioned by the law. But if alternative ciphertexts can be made to be indistinguishable from standard ones, such persons may never be exposed since their encrypted traffic will perfectly "blend in" with that of millions of legitimate users.
The gravity of this problem may not be underestimated. If not adequately prevented, the indistinguishability of ciphertexts produced by approved and non-approved cryptosystems will be a major criminal threat. Some proposed solutions to this crucial problem are discussed below.
One tentative solution (discussed both by Fair Cryptosystems and the Clipper Chip) consists of putting the chosen encryption algorithm in a secure or tamper-proof piece of hardware; e.g., a chip (some portion of) which cannot be read from the outside and cannot be tampered with (since any tampering would result in destroying the information protected inside). This approach has some important advantages. For instance, use of tamper-proof hardware makes it impossible for an adversary to use the chosen cryptosystem with a new secret key. Thus, if the adversary really wants to use a different key, he must also get hold of a different piece of encryption equipment, which may be difficult. Indeed, it is conceivable that Government-approved, inexpensive encryption hardware will be readily available or part of telephones, faxes, computers and other devices. On the other hand, finding or having manufactured "alternative" and ad hoc encryption equipment may be sufficiently inconvenient for most adversaries. Indeed, it would be very desirable if law-abiding citizens could legitimately use encryption with great ease, while criminals could misuse encryption only at the price of great inconvenience.
A second approach (also addressed in Fair Cryptosystems and the Clipper Chip) envisions that the secure hardware containing the chosen cryptosystem also contains (possibly in addition to the user's secret key) a key K secret, but available to the proper authorities. The key K resides within the secure hardware and thus cannot be read from the outside. After the approved equipment produces a ciphertext C, a corresponding authentication tag T may be computed by means of this additional key. For instance, T may be a (preferably short) string computed as a function of C and K, and thus T cannot be computed by an adversary who does not use Government-approved encryption equipment, because he does not know the value of K. The key K need not be unique for all Government-approved devices, but could be device-specific. The advantage of this approach is that an adversary who encrypts without using the Government-approved devices may be detected. Indeed, if a spy encrypts his communications with a non-approved device, he cannot add the right authentication tags to the ciphertexts he produces. Thus, if encrypted communications are monitored, whenever a communication lacks the right tag, it will become clear that communication was produced by a non-approved device. Therefore, although the proper authorities may never be able to understand the meaning of that communication, it may be helpful to them to be aware of the presence of someone who goes out of his way, incurring great inconvenience, in order to avoid using Government-approved encryption devices.
These techniques, however, do not provide adequate proof that a given ciphertext has been provided by an approved piece of encryption equipment. In particular, they suffer from the so-called "double encryption" security problem. This problem can be described as follows. Assume two persons X and Y first encrypt a message M with a key known only to them (and possibly also with a cryptosystem of their own) so as to obtain a ciphertext M'. They then encrypt M' with a piece of Government-approved equipment so as to produce a second ciphertext M". By doing so, the two persons understand M. The recipient of M" may use the Government-approved system to retrieve M', and then the special system between X and Y to compute M from M'. To the contrary, if law enforcement officials legitimately try to recover M from M", they will fail. This is because while they can reconstruct M' from M", they cannot compute M from M' because M' is not an encryption of M obtained with the Government-approved system. Indeed, even if the Government-approved equipment produces authentication tags, the encrypted communications between X and Y will appear to-be totally legitimate--even though no law-enforcement officer will ever understand them.
Indeed, when X (or Y) feeds M' to the Government-approved encryption equipment, the equipment will produce not only M" but also a valid authentication tag T" for M". This is because such authentication tags "expose" only an adversary who never uses the Government-approved cryptosystem. But in a double-encryption attack, the enemy uses the Government-approved equipment, though in a special fashion. And it is well-known that the Clipper Chip, for example, is powerless against such double-encryption attacks.